/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package algoritmos_busqueda;

/**
 *
 * @author Esteban
 */
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
import javax.swing.JOptionPane;


public class BusquedaBackwardLPAStar extends Thread {

    ComparadorCola comparadorCola = new ComparadorCola();
    PriorityQueue <Cuadrado> cola = new PriorityQueue(1000, comparadorCola);

    Mapa mapa;

    public BusquedaBackwardLPAStar(Mapa m)
    {
        mapa = m;
    }

    private void calcularClaveLP(Cuadrado c)
    {
        int[] valor = new int[2];
        mapa.obtenerBDistanciaManhatan(c);
        valor[0] = Math.min(c.obtenerG(), c.obtenerrhs()) + c.obtenerH();
        valor[1] = Math.min(c.obtenerG(), c.obtenerrhs());
        c.establecerClaveLP(valor);
    }

    private void iniciar()
    {
        cola.clear();
        Cuadrado destino = mapa.obtenerDestino();
        for(int a=0;a<25;a++)
        {
            for (int b=0;b<25;b++)
            {
                mapa.obtenercuadrado(b, a).establecerG(700); //Se toma 700 como infinito
                mapa.obtenercuadrado(b, a).establecerH(mapa.obtenerBDistanciaManhatan(mapa.obtenercuadrado(b, a)));
                mapa.obtenercuadrado(b, a).establecerrhs(700);
            }
        }
        destino.establecerrhs(0);
        //origen.establecerG(0);
        //Truco del algoritmo:
        //No se establece g a 0 para que en la primera iteracion de busCamino se cumpla que g > rhs
        calcularClaveLP(destino);
        cola.add(destino);
    }

    private void actualizarCuadrado(Cuadrado c)
    {
        Cuadrado destino = mapa.obtenerDestino();
        if (!c.equals(destino)) //c.establecerrhs(c.obtenerpredecesor().obtenerG() + c.obtenerDificultad());
        {
            int valorminimo = 0;

            List<Cuadrado> vecinos = new ArrayList<Cuadrado>();
                vecinos = mapa.obtenervecinos(c);
                Iterator iteradorVecinos = vecinos.iterator();
                if (iteradorVecinos.hasNext())
                {
                    Cuadrado vecinoActual = (Cuadrado) iteradorVecinos.next();
                    valorminimo = vecinoActual.obtenerG() + c.obtenerDificultad();
                }

                while(iteradorVecinos.hasNext())
                {
                    Cuadrado vecinoActual = (Cuadrado) iteradorVecinos.next();
                    if (vecinoActual.obtenerG() + c.obtenerDificultad() < valorminimo) valorminimo = vecinoActual.obtenerG() + c.obtenerDificultad();
                }

                c.establecerrhs(valorminimo);
        }
        if (cola.contains(c)) cola.remove(c);
        if (c.obtenerG() != c.obtenerrhs())
        {
            calcularClaveLP(c);
            cola.add(c);
            //System.out.println("elemento añadido");
        }
    }

    private void buscarCamino()
    {
        calcularClaveLP(mapa.obtenerorigen());
        while((comparadorCola.compare(cola.peek(), mapa.obtenerorigen()) < 0) || (mapa.obtenerorigen().obtenerrhs() != mapa.obtenerorigen().obtenerG())) //(comparadorCola.compare(cola.peek(), mapa.obtenerDestino()) < 0) ||
        {

            Cuadrado cuadradoActual = cola.poll();
            cuadradoActual.pintar(1);
            //JOptionPane.showMessageDialog(null, cuadradoActual.obtenerG());
            if (cuadradoActual.obtenerG() > cuadradoActual.obtenerrhs())
            {
                cuadradoActual.establecerG(cuadradoActual.obtenerrhs());
                List<Cuadrado> vecinos = new ArrayList<Cuadrado>();
                vecinos = mapa.obtenervecinos(cuadradoActual);
                Iterator iteradorVecinos = vecinos.iterator();
                while(iteradorVecinos.hasNext())
                {
                    Cuadrado vecinoActual = (Cuadrado) iteradorVecinos.next();

                    //JOptionPane.showMessageDialog(null, "basura1");
                    vecinoActual.pintar(1);
                    if (!vecinoActual.equals(mapa.obtenerorigen()) ) vecinoActual.establecerpredecesor(cuadradoActual);
                    actualizarCuadrado(vecinoActual);
                }
            }
            else
            {
                cuadradoActual.establecerG(700);
                actualizarCuadrado(cuadradoActual);
                List<Cuadrado> vecinos = new ArrayList<Cuadrado>();
                vecinos = mapa.obtenervecinos(cuadradoActual);
                Iterator iteradorVecinos = vecinos.iterator();
                while(iteradorVecinos.hasNext())
                {
                    Cuadrado vecinoActual = (Cuadrado) iteradorVecinos.next();

                    //JOptionPane.showMessageDialog(null, "basura2");
                    vecinoActual.pintar(1);
                    if (!vecinoActual.equals(mapa.obtenerorigen())) vecinoActual.establecerpredecesor(cuadradoActual);
                    actualizarCuadrado(vecinoActual);
                }
            }
            calcularClaveLP(mapa.obtenerDestino());
            if (cola.isEmpty()) System.out.println("Cola vacia");
            try
            {
                Thread.currentThread().sleep(101 - Ventana.velocidadPersonaje);
            }
            catch(Exception e)
            {

            }
            while(Ventana.velocidadPersonaje == 0)
            {
                try
            {
                Thread.currentThread().sleep(10);
            }
            catch(Exception e)
            {

            }
            }
        }
    }

    public void dibujarCamino()
    {
        Cuadrado cuadradoActual = mapa.obtenerorigen();
        int gActual = cuadradoActual.obtenerG();

        while(cuadradoActual != mapa.obtenerDestino())
        {
            cuadradoActual.pintar(2);

            //Aqui se sigue el camino de G hasta llegar a la minima G (el origen).
            List<Cuadrado> vecinos = new ArrayList<Cuadrado>();
                vecinos = mapa.obtenervecinos(cuadradoActual);
                Iterator iteradorVecinos = vecinos.iterator();
                while(iteradorVecinos.hasNext())
                {
                    Cuadrado vecinoActual = (Cuadrado) iteradorVecinos.next();
                    if (vecinoActual.obtenerG() < gActual)
                    {
                        gActual = vecinoActual.obtenerG();
                        cuadradoActual = vecinoActual;
                    }
                }



            try
            {
                Thread.currentThread().sleep(101 - Ventana.velocidadPersonaje);
            }
            catch(Exception e)
            {

            }
            while(Ventana.velocidadPersonaje == 0)
            {
                try
            {
                Thread.currentThread().sleep(10);
            }
            catch(Exception e)
            {

            }
            }
        }
        cuadradoActual.pintar(2);

    }

    private Cuadrado esperarCambio()
    {
        int[][] tableroTemp = new int [25][25];
        boolean cambio = false;

        for (int a = 0 ; a<25; a++)
            {
                for (int b = 0 ; b<25; b++)
                {
                    tableroTemp[b][a] = mapa.obtenercuadrado(b, a).obtenerDificultad();
                }
            }



        while(!cambio)
        {
            for (int a = 0 ; a<25; a++)
            {
                for (int b = 0 ; b<25; b++)
                {
                    if (mapa.obtenercuadrado(b, a).obtenerDificultad() != tableroTemp[b][a])
                    {
                        cambio = true;
                        return mapa.obtenercuadrado(b, a);
                    }

                }
            }
        }
        return null;


    }


    public void run()
    {
        iniciar();
        while(true)
        {
            buscarCamino();
            dibujarCamino();
            Cuadrado cambio = esperarCambio();
            System.out.println("cambio");
            if (!cambio.esobstaculo()) actualizarCuadrado(cambio);
            List<Cuadrado> vecinosCambiados = new ArrayList<Cuadrado>();
            vecinosCambiados = mapa.obtenervecinos(cambio);
            Iterator iteradorVecinos = vecinosCambiados.iterator();
            while(iteradorVecinos.hasNext())
            {
                Cuadrado vecinoActual = (Cuadrado) iteradorVecinos.next();
                actualizarCuadrado(vecinoActual);

            }

        }

    }



    class ComparadorCola implements Comparator
    {
        public int compare(Object c1, Object c2)
        {
            if ( (!(c1 instanceof Cuadrado)) && (!(c2 instanceof Cuadrado))) return 0;
            Cuadrado cuadrado1 = (Cuadrado) c1;
            Cuadrado cuadrado2 = (Cuadrado) c2;

            int[] k1 = cuadrado1.obtenerclaveLP();

            int[] k2 = cuadrado2.obtenerclaveLP();

            if (k1[0] < k2[0]) {
                return -1;
            } else if (k1[0] > k2[0]) {
                return 1;
            } else {
                if (k1[1] < k2[1]) {
                    return -1;
                } else if (k1[1] > k2[1]) {
                    return 1;
                } else {
                    return 0;
                }
            }


            /*if( k1[0] < k2[0] ){
                return -1;
            }else if( k1[0] == k2[0] && k1[1] < k2[1] ){
                return -1;
            }else if( k1[0] == k2[0] && k1[1] == k2[1] && cuadrado1.obtenerx() < cuadrado2.obtenerx()){
                return -1;
            }else if( k1[0] == k2[0] && k1[1] == k2[1] && cuadrado1.obtenerx() == cuadrado2.obtenerx() && cuadrado1.obtenery() < cuadrado2.obtenery() ){
                return -1;
            }else if( k1[0] == k2[0] && k1[1] == k2[1] && cuadrado1.obtenerx() == cuadrado2.obtenerx() && cuadrado1.obtenery() == cuadrado2.obtenery() ){
                return 0;
            }else{
                return 1;
            }*/




        }
    }
}

